package caculate.strSearch;

import java.util.Arrays;

/**
 * @program: rocsun
 * @description:
 * @author: yx.guo
 * @create: 2025-02-28 12:39
 **/
public class KMP extends StrMethod {

    public KMP(String str, String pattern) {
        super(str, pattern);
    }

    @Override
    public int searchStr() {
        int[] next = new int[pLen];
        buildNext(next);
        int i;
        int j = 0;
        for (i = 0; i < sLen; i++) {
            while (j > 0 && str.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }

            if (str.charAt(i) == pattern.charAt(j)) {
                j++;
            }

            if (j == pLen) {
                return i - pLen + 1;
            }
        }

        return -1;
    }

    /**
     * 构建next数组，存放当前位置子串的最大公共前后缀最后一个字符的下标
     * @param next
     */
    private void buildNext(int[] next) {
        Arrays.fill(next, 0); // 默认妹子位置的最长前后缀都不存在

        int i = 1;
        int j = 0;
        while (i < pLen) {
            while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
                j = next[j - 1];
            }

            if (pattern.charAt(j) == pattern.charAt(i)) {
                j++;
            }

            next[i++] = j;
        }
    }

}
